{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 贝叶斯分类器\n",
    "&emsp;&emsp;上篇主要介绍和讨论了支持向量机。从最初的分类函数，通过最大化分类间隔，$\\displaystyle \\max(\\frac{1}{\\|w\\|}),\\min(\\frac{1}{2}\\|w\\|^2)$，凸二次规划，拉格朗日函数，对偶问题，一直到最后的SMO算法求解，都为寻找一个最优解。接着引入核函数将低维空间映射到高维特征空间，解决了非线性可分的情形。最后介绍了软间隔支持向量机，解决了outlier挤歪超平面的问题。本篇将讨论一个经典的统计学习算法——**贝叶斯分类器**。  \n",
    "&emsp;&emsp;贝叶斯分类器是一种概率框架下的统计学习分类器，对分类任务而言，假设在相关概率都已知的情况下，贝叶斯分类器考虑如何基于这些概率为样本判定最优的类标。在开始介绍贝叶斯决策论之前，我们首先来回顾下“概率论委员会常委”——贝叶斯公式。  \n",
    "> **定理：**设试验$E$的样本空间为$S$，$A$为$E$的事件，$B_1,B_2,\\cdots,B_n$为$S$的一个划分，且$P(A)>0,P(B_i)>0(i=1,2,\\cdots,n)，$则$$P(B_i|A)=\\frac{P(A|B_i)P(B_i)}{\\displaystyle \\sum_{j=1}^n P(A|B_i)P(B_i)}, \\quad i=1,2,\\cdots,n$$称为**贝叶斯(Bayes)公式**。（实际上由条件概率与全概率推导出）\n",
    "\n",
    "### 贝叶斯决策论\n",
    "&emsp;&emsp;若将上述定义中样本空间的划分$B_i$看做为类标（类别标记），$A$看做为一个新的样本，则很容易将条件概率理解为样本$A$是类别$B_i$的概率。在机器学习训练模型的过程中，往往我们都试图去优化一个风险函数，因此在概率框架下我们也可以为贝叶斯定义“**条件风险**”（conditional risk）。$$R(c_i|x)=\\sum_{j=1}^N \\lambda_{ij}P(c_j|x)$$其中$\\lambda$表示损失。  \n",
    "&emsp;&emsp;我们的任务就是寻找一个判定准则最小化所有样本的条件风险总和，因此就有了**贝叶斯判定准则**（Bayes decision rule）——最小化总体风险，只需在每个样本上选择那个使得条件风险最小的类标。$$h^*(x)=\\underset{c \\in \\mathcal{Y}}{\\arg \\min } R(c | x)$$若损失函数λ取0-1损失，则有：$${R(c | x)=1-P(c | x)} \\\\ {h^*(x)=\\underset{c \\in \\mathcal{Y}}{\\arg \\max } P(c|x)}$$&emsp;&emsp;即对于每个样本$x$，选择其后验概率$P(c|x)$最大所对应的类标，能使得总体风险函数最小，从而将原问题转化为估计后验概率$P(c|x)$。一般这里有两种策略来对后验概率进行估计：\n",
    "\n",
    "- 判别式模型：直接对$P(c|x)$进行建模求解。例我们前面所介绍的决策树、神经网络、SVM都是属于判别式模型。  \n",
    "- 生成式模型：通过先对联合分布$P(x,c)$建模，从而进一步求解$P(c|x)$。\n",
    "\n",
    "&emsp;&emsp;贝叶斯分类器就属于生成式模型，基于贝叶斯公式对后验概率$P(c|x)$进行一项神奇的变换，巴拉拉能量....$P(c|x)$变身：$$P(c|x)=\\frac{P(c)P(x|c)}{P(x)}$$其中$P(c)$表示类先验概率，$P(x|c)$表示类条件概率或似然，$P(x)$表示证据因子。  \n",
    "&emsp;&emsp;对于给定的样本$x$，$P(x)$与类标无关，$P(c)$称为类先验概率，$P(x|c)$称为类条件概率。这时估计后验概率$P(c|x)$就变成为估计类先验概率和类条件概率的问题。对于先验概率和后验概率，在看这章之前也是模糊了我好久，这里普及一下它们的基本概念。\n",
    "\n",
    "- 先验概率： 根据以往经验和分析得到的概率。\n",
    "- 后验概率：后验概率是基于新的信息，修正原来的先验概率后所获得的更接近实际情况的概率估计。\n",
    "\n",
    "&emsp;&emsp;实际上先验概率就是在没有任何结果出来的情况下估计的概率，而后验概率则是在有一定依据后的重新估计，直观意义上后验概率就是条件概率。下面直接上Wiki上的一个例子，简单粗暴快速完事...\n",
    "\n",
    "> 假设一个学校里有60%男生和40%女生，女生穿裤子的人数和穿裙子的人数相等，所有男生穿裤子，一个人在远处随机看到了一个穿裤子的学生，那么这个学生是女生的概率是多少？  \n",
    "解答：使用贝叶斯定理，事件$A$是看到女生，事件$B$是看到一个穿裤子的学生，我们所要计算的是$P(A|B)$。  \n",
    "$P(A)$是忽略其他因素，看到女生的概率，在这里是40%。  \n",
    "$P(A')$是忽略其他因素，看到不是女生（即看到男生）的概率，在这里是60%。  \n",
    "$P(B|A)$是女生穿裤子的概率，在这里是50%。  \n",
    "$P(B|A')$是男生传裤子的概率，在这里是100%。  \n",
    "$P(B)$是忽略其他因素，学生穿裤子的概率，$P(B)=P(B|A)P(A)+P(B|A')P(A')$，在这里是$0.5 \\times 0.4 + 1 \\times 0.6 = 0.8$  \n",
    "根据贝叶斯定理，我们计算出后验概率$P(A|B)$：$$P(A|B)= \\frac{P(B|A)P(A)}{P(B)}=\\frac{0.5 \\times 0.4}{0.8}=0.25$$可见，**后验概率实际上就是条件概率**。\n",
    "\n",
    "&emsp;&emsp;回归正题，对于类先验概率$P(c)$，$P(c)$就是样本空间中各类样本所占的比例，根据大数定理（当样本足够多时，频率趋于稳定等于其概率），这样当训练样本充足时，$P(c)$可以使用各类出现的频率来代替。因此只剩下类条件概率$P(x|c)$，它表达的意思是在类别$c$中出现$x$的概率，它涉及到属性的联合概率问题，若只有一个离散属性还好，当属性多时采用频率估计起来就十分困难，因此这里一般采用极大似然法进行估计。\n",
    "\n",
    "### 极大似然法\n",
    "&emsp;&emsp;极大似然估计（Maximum Likelihood Estimation，简称MLE），是一种根据数据采样来估计概率分布的经典方法。常用的策略是先假定总体具有某种确定的概率分布，再基于训练样本对概率分布的参数进行估计。运用到类条件概率$p(x|c)$中，假设$p(x|c)$服从一个参数为$\\theta$的分布，问题就变为根据已知的训练样本来估计$\\theta$。极大似然法的核心思想就是：估计出的参数使得已知样本出现的概率最大，即使得训练数据的似然最大。\n",
    "\n",
    "> 令$D_c$表示训练集$D$中第$c$类样本组成的集合，假设这些样本是独立同分布的（统计学的基础假设），则参数$\\theta_c$对于数据集$D_c$的似然是$$P(D_c | \\theta_c)=\\prod_{x \\in D_c} P(x | \\theta_c)$$连乘操作使得求解变得十分复杂，一般我们使用对数似然（log-likelihood）:$$\\begin{aligned} L L(\\theta_c) &=\\log P(D_c | \\theta_c) \\\\\n",
    "&=\\sum_{x \\in D_c} \\log P(x | \\theta_c) \\end{aligned}$$此时参数$\\theta_c$的极大似然估计$\\hat{\\theta_c}$为：$$\\hat{\\theta}_c=\\underset{\\theta_c}{\\arg \\max } L L(\\theta_c)$$一般采用对每个参数求偏导等于0的方法求解。\n",
    "\n",
    "&emsp;&emsp;所以，贝叶斯分类器的训练过程就是参数估计。总结最大似然法估计参数的过程，一般分为以下四个步骤：\n",
    "\n",
    "1. 写出似然函数；\n",
    "2. 对似然函数取对数，并整理；\n",
    "3. 求导数，令偏导数为$\\theta$，得到似然方程组；\n",
    "4. 解似然方程组，得到所有参数即为所求。\n",
    "\n",
    "例如：假设样本属性都是连续值，$p(x|c)$服从一个多维高斯分布，则通过MLE计算出的参数刚好分别为：$$p(x|c) \\sim \\mathcal{N}(\\mu_c, \\sigma_c^2) \\\\ \n",
    "样本均值向量：\\hat{\\mu}_c=\\frac{1}{|D_c|} \\sum_{x \\in D_c} x \\\\\n",
    "样本协方差矩阵：\\hat{\\sigma}_c^2=\\frac{1}{|D_c|} \\sum_{x \\in D_c}(x-\\hat{\\mu_c})(x-\\hat{\\mu}_c)^T$$&emsp;&emsp;上述结果看起来十分合乎实际，但是采用最大似然法估计参数的效果很大程度上依赖于作出的假设是否合理，是否符合潜在的真实数据分布。这就需要大量的经验知识，搞统计越来越值钱也是这个道理，大牛们掐指一算比我们搬砖几天更有效果。\n",
    "\n",
    "### 朴素贝叶斯分类器\n",
    "&emsp;&emsp;不难看出：原始的贝叶斯分类器最大的问题在于联合概率密度函数的估计，首先需要根据经验来假设联合概率分布，其次当属性很多时，训练样本往往覆盖不够，参数的估计会出现很大的偏差。为了避免这个问题，朴素贝叶斯分类器（naive Bayes classifier）采用了“属性条件独立性假设”，即样本数据的所有属性之间相互独立。这样类条件概率$p(x|c)$可以改写为：$$P(x | c)=\\prod_{i=1}^{d} P(x_i | c)$$&emsp;&emsp;这样，为每个样本估计类条件概率变成为每个样本的每个属性估计类条件概率。\n",
    "\n",
    "- 对于**离散属性**，属性的类条件概率可估计为：$\\displaystyle P(x_i | c) = \\frac{|D_{c,x_i}|}{|D_c|}$  \n",
    "- 对于**连续属性**，若假设属性服从正态分布，则属性的类条件概率可估计为：$\\displaystyle p(x_i|c)=\\frac{1}{\\sqrt{2\\pi} \\sigma_{c,i}} \\exp\\left( -\\frac{(x_i-\\mu_{c,i})^2}{2 \\sigma_{c,i}^2}\\right)$\n",
    "\n",
    "&emsp;&emsp;相比原始贝叶斯分类器，朴素贝叶斯分类器基于单个的属性计算类条件概率更加容易操作，需要注意的是：若某个属性值在训练集中和某个类别没有一起出现过，这样会抹掉其它的属性信息，因为该样本的类条件概率被计算为0。因此在估计概率值时，常常用进行平滑（smoothing）处理，拉普拉斯修正（Laplacian correction）就是其中的一种经典方法，具体计算方法如下：$$\n",
    "\\begin{aligned} \\hat{P}(c) &=\\frac{|D_c|+1}{|D|+N} \\\\\n",
    "\\hat{P}(x_i | c) &=\\frac{|D_{c, x_i}|+1}{|D_c|+N_i} \\end{aligned}$$&emsp;&emsp;当训练集越大时，拉普拉斯修正引入的影响越来越小。对于贝叶斯分类器，模型的训练就是参数估计，因此可以事先将所有的概率储存好，当有新样本需要判定时，直接查表计算即可。  \n",
    "&emsp;&emsp;针对朴素贝叶斯，人们觉得它too sample，sometimes too naive！因此又提出了半朴素的贝叶斯分类器，具体有SPODE、TAN、贝叶斯网络等来刻画属性之间的依赖关系，此处不进行深入，等哪天和贝叶斯邂逅了再回来讨论。在此鼎鼎大名的贝叶斯介绍完毕，下一篇将介绍这一章剩下的内容——EM算法，朴素贝叶斯和EM算法同为数据挖掘的十大经典算法，想着还是单独介绍吧~\n",
    "\n",
    "### EM算法\n",
    "&emsp;&emsp;上篇主要介绍了贝叶斯分类器，从贝叶斯公式到贝叶斯决策论，再到通过极大似然法估计类条件概率，贝叶斯分类器的训练就是参数估计的过程。朴素贝叶斯则是“属性条件独立性假设”下的特例，它避免了假设属性联合分布过于经验性和训练集不足引起参数估计较大偏差两个大问题，最后介绍的拉普拉斯修正将概率值进行平滑处理。本篇将介绍另一个当选为数据挖掘十大算法之一的**EM算法**。  \n",
    "&emsp;&emsp;EM（Expectation-Maximization）算法是一种常用的估计参数隐变量的利器，也称为“期望最大算法”，是数据挖掘的十大经典算法之一。EM算法主要应用于训练集样本不完整即存在隐变量时的情形（例如某个属性值未知），通过其独特的“两步走”策略能较好地估计出隐变量的值。\n",
    "\n",
    "#### EM算法思想\n",
    "&emsp;&emsp;EM是一种迭代式的方法，它的基本思想就是：若样本服从的分布参数$\\theta$已知，则可以根据已观测到的训练样本推断出隐变量$Z$的期望值（E步），若$Z$的值已知则运用最大似然法估计出新的$\\theta$值（M步）。重复这个过程直到$Z$和$\\theta$值不再发生变化。  \n",
    "&emsp;&emsp;简单来讲：假设我们想估计$A$和$B$这两个参数，在开始状态下二者都是未知的，但如果知道了$A$的信息就可以得到B的信息，反过来知道了$B$也就得到了$A$。可以考虑首先赋予$A$某种初值，以此得到$B$的估计值，然后从$B$的当前值出发，重新估计$A$的取值，这个过程一直持续到收敛为止。\n",
    "\n",
    "- 基于$\\Theta^t$推断隐变量$Z$的期望，记为$Z^t$；  \n",
    "- 基于已观测变量$X$和$Z^t$对参数$\\Theta$做极大似然估计，记为$\\Theta^{t+1}$；\n",
    "\n",
    "&emsp;&emsp;现在再来回想聚类的代表算法K-Means：【首先随机选择类中心$\\Rightarrow$将样本点划分到类簇中$\\Rightarrow$重新计算类中心$\\Rightarrow$不断迭代直至收敛】，不难发现这个过程和EM迭代的方法极其相似，事实上，若将样本的类别看做为“隐变量”（latent variable）$Z$，类中心看作样本的分布参数$\\theta$，K-Means就是通过EM算法来进行迭代的，与我们这里不同的是，K-Means的目标是最小化样本点到其对应类中心的距离和，上述为极大化似然函数。\n",
    "\n",
    "#### EM算法数学推导\n",
    "&emsp;&emsp;在上篇极大似然法中，当样本属性值都已知时，我们很容易通过极大化对数似然，接着对每个参数求偏导计算出参数的值。但当存在隐变量时，就无法直接求解，此时我们通常最大化已观察数据的对数“边际似然”（marginal likelihood）。$$L L(\\Theta | X)=\\ln P(X | \\Theta)=\\ln \\sum_{Z} P(X, Z | \\Theta)\\quad \\text{同边缘密度函数一样}$$&emsp;&emsp;这时候，通过边缘似然将隐变量$Z$引入进来，对于参数估计，现在与最大似然不同的只是似然函数式中多了一个未知的变量$Z$，也就是说我们的目标是找到适合的$\\theta$和$Z$让$L(\\theta)$最大，这样我们也可以分别对未知的$\\theta$和$Z$求偏导，再令其等于0。  \n",
    "&emsp;&emsp;然而观察上式可以发现，和的对数（$\\ln(x_1+x_2+x_3)$）求导十分复杂，那能否通过变换上式得到一种求导简单的新表达式呢？这时候 Jensen不等式就派上用场了，先回顾一下高等数学凸函数的内容：  \n",
    "> **Jensen's inequality**：过一个凸函数上任意两点所作割线一定在这两点间的函数图象的上方。理解起来也十分简单，对于凸函数$f(x)''>0$，即曲线的变化率是越来越大单调递增的，所以函数越到后面增长越厉害，这样在一个区间下，函数的均值就会大一些了。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/7-1-Jensen's-Inequality-for-Convex-Function.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-1 Jensen's Inequality</div></center>\n",
    "\n",
    "&emsp;&emsp;因为$ln(\\cdot)$函数为凹函数，故可以将上式“和的对数”变为“对数的和”，这样就很容易求导了。\n",
    "$$\\begin{aligned} \\sum_i \\log p(x^{(i)};\\theta) \n",
    "&= \\sum_i \\log \\sum_{z^{(i)}} p(x^{(i)}, z^{(i)};\\theta) \\\\\n",
    "&= \\sum_i \\log \\sum_{z^{(i)}} Q_i(z^{(i)}) \\frac{p(x^{(i)}, z^{(i)};\\theta)}{Q_i(z^{(i)})} \\\\\n",
    "& \\geqslant \\sum_i \\sum_{z^{(i)}} Q_i(z^{(i)}) \\log \\frac{p(x^{(i)}, z^{(i)};\\theta)}{Q_i(z^{(i)})}\n",
    "\\end{aligned}$$&emsp;&emsp;接着求解$Q_i$和$\\theta$：首先固定$\\theta$（初始值），通过求解$Q_i$使得$J(\\theta，Q)$在$\\theta$处与$L(\\theta)$相等，即求出$L(\\theta)$的下界；然后再固定$Q_i$，调整$\\theta$，最大化下界$J(\\theta，Q)$。不断重复两个步骤直到稳定。通过Jensen不等式的性质，$Q_i$的计算公式实际上就是后验概率：$$\\begin{aligned} Q_i (z^{(i)}) \n",
    "&=\\frac{p (x^{(i)}, z^{(i)} ; \\theta)}{\\displaystyle \\sum_z p(x^{(i)}, z ; \\theta)} \\\\ \n",
    "&=\\frac{p(x^{(i)}, z^{(i)} ; \\theta)}{p(x^{(i)} ; \\theta)} \\\\ \n",
    "&=p(z^{(i)} | x^{(i)} ; \\theta) \\end{aligned}$$&emsp;&emsp;通过数学公式的推导，简单来理解这一过程：固定$\\theta$计算$Q$的过程就是在建立$L(\\theta)$的下界，即通过Jenson不等式得到的下界（E步）；固定$Q$计算$\\theta$则是使得下界极大化（M步），从而不断推高边缘似然$L(\\theta)$。从而循序渐进地计算出$L(\\theta)$取得极大值时隐变量$Z$的估计值。  \n",
    "&emsp;&emsp;EM算法也可以看作一种“坐标下降法”，首先固定一个值，对另外一个值求极值，不断重复直到收敛。这时候也许大家就有疑问，问什么不直接这两个家伙求偏导用梯度下降呢？这时候就是坐标下降的优势，有些特殊的函数，例如曲线函数$z=y^2+x^2+x^2y+xy+\\ldots$，无法直接求导，这时如果先固定其中的一个变量，再对另一个变量求极值，则变得可行。  \n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/7-2-Coordinate-Descent.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-2 坐标下降法</div></center>\n",
    "\n",
    "#### EM算法流程\n",
    "&emsp;&emsp;看完数学推导，算法的流程也就十分简单了，这里有两个版本，版本一来自西瓜书，作者的介绍十分简洁；版本二来自于大牛的博客。结合着数学推导，自认为版本二更具有逻辑性，两者唯一的区别就在于版本二多出了红框的部分，这里我（原作者）也没得到答案，欢迎讨论\n",
    "**版本一：**\n",
    "> - E步（Expectation）：以当前参数$\\Theta^t$推断隐变量分布$P(Z|X,\\Theta^t)$，并计算对数似然$LL(\\Theta | X,Z)$关于$Z$的$$Q(\\Theta | \\Theta^{t})=\\mathbb{E}_{Z | X, \\Theta^t} L L(\\Theta | X, Z)$$ \n",
    "- M步（Maximization）：寻找参数最大化期望似然，即$$\\Theta^{t+1}=\\underset{\\Theta}{\\arg \\max } Q(\\Theta | \\Theta^t)$$  \n",
    "\n",
    "**版本二：**  \n",
    "> **E步骤：**根据参数初始化或上一次迭代的模型参数来计算出隐变量的后验概率，其实就是隐变量的期望。作为隐变量的现估计值：$$Q_{i}(z^{(i)}) := p(z^{(i)} | x^{(i)} ; \\theta)$$**M步骤：**将似然函数最大化以获得新的参数值：$$\n",
    "\\theta :=\\arg \\max_{\\theta} \\sum_i \\sum_{z^{(i)}} Q_i (z^{(i)}) \\log \\frac{p(x^{(i)}, z^{(i)} ; \\theta)}{Q_i (z^{(i)})}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
